package util.queue;

import java.lang.reflect.Array;

/**
 * 循环队列
 * @author Huzz
 * @created 2021-10-15 19:1
 */
public class LoopQueue<T> {

    private static final int DEFAULT_SIZE = 128;

    /**
     * 存放队元素的数组
     */
    private T[] queueList;

    /**
     * 头指针
     */
    private int front;
    /**
     * 尾指针
     */
    private int rear;
    /**
     * 最大长度
     */
    private int maxSize;

    /**
     * 初始化队列
     */
    public LoopQueue(Class<T> type) {
        this(type, DEFAULT_SIZE);
    }

    public LoopQueue(Class<T> type, int size) {
        queueList = (T[]) Array.newInstance(type, size + 1);
        rear = 0;
        front = 0;
        // 多分配一个空间用于确定队满和队空情况
        maxSize = size + 1;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * 判断队列是否已满
     *
     * @return
     */
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * 取循环队列的对首元素
     *
     * @return
     */
    public Object getFront() {
        return queueList[front];
    }

    /**
     * 入队
     *
     * @param val
     */
    public void push(T val) {
        if (isFull()) {
            throw new IndexOutOfBoundsException();
        }
        // 入队操作. 队满时抛出异常
        queueList[rear] = val;
        rear = (rear + 1) % maxSize;
    }

    /**
     * 出队
     */
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        T result = queueList[front];
        front = (front + 1) % maxSize;
        return result;
    }

    /**
     * 获取队列长度
     *
     * @return
     */
    public int size() {
        // 1. 当头指针小于尾指针时，长度：len1 = rear - front
        // 2. 当头指针大于尾指针时，说明队列从第二圈开始了,
        //    空元素段为：front - rear 所以有元素段 maxSize - (front - rear) => len2 = maxSize + front - rear
        // 3. 利用同一个表达式表示这两种情况,其中n表示整数常量： (rear - front) + (n * maxSize) % maxSize
        return (rear - front + maxSize) % maxSize;
    }

}